Linked list cycle II

Time: O(N); Space: O(1); medium

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note:

  • Do not modify the linked list.

Example 1:

Input: head = {ListNode} 3->2->0->-4->None

Output: 2 (tail connects to node index 1)

Explanation:

  • There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = {ListNode} 1->2->None

Output: 1 (tail connects to node index 0)

Explanation:

  • There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = {ListNode} 1->None

Output: None

Explanation:

  • There is no cycle in the linked list.

Follow-up:

  • Can you solve it without using extra space?

[11]:

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

    def __str__(self):
        if self:
            return "{}".format(self.val)
        else:
            return None

[12]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return None

        fast, slow = head, head

        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
            if fast is slow:
                fast = head
                while fast is not slow:
                    fast, slow = fast.next, slow.next
                return fast

        return None

[14]:

s = Solution1()

head = ListNode(3)
head.next = ListNode(2)
head.next.next = ListNode(0)
head.next.next.next = ListNode(-4)
head.next.next.next.next = head.next
assert s.detectCycle(head).val == 2

head = ListNode(1)
head.next = ListNode(2)
head.next.next = head
assert s.detectCycle(head).val == 1

head = ListNode(1)
assert s.detectCycle(head) == None